package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type MyNode struct {
	tree    *TreeNode
	visited bool
}

// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
func preorderTraversal(root *TreeNode) []int {
	stack := []*MyNode{
		{tree: root, visited: false},
	}
	result := []int{}
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if top.tree == nil {
			continue
		}
		if !top.visited {
			stack = append(stack, &MyNode{tree: top.tree.Right, visited: false})
			stack = append(stack, &MyNode{tree: top.tree.Left, visited: false})
			stack = append(stack, &MyNode{tree: top.tree, visited: true})
		} else {
			if top.tree != nil {
				result = append(result, top.tree.Val)
			}
		}
	}
	return result
}

func main() {

}
